1. Field of Invention
This invention relates to the field of machine vision and more precisely to pattern matching.
2. Discussion of Related Art
When using present pattern matching techniques, there are situations where it is possible to incorrectly select a match for a model in a target image among a set of occurrences. Examples of such situations are illustrated below.
FIGS. 3a, 1a, 1b and 1c together illustrate an example where more than one occurrence of a model is detected in a target image when using prior art techniques. Referring to FIG. 3a, the model is defined by a set of primitives 16, as in methods known in the art. For the purposes of this description, the foregoing primitives will be referred to herein as additive primitives. The dotted lines around the model primitives 16 are illustrative only and indicate that a blank space to the left of the model primitives 16 is being sought. However, this blank space is not defined in the model.
In the target image, the likelihood of a match at a given location is measured using a similarity score, which computes the proportion of model primitives appearing at this location. In the situation illustrated in FIGS. 1a, 1b and 1c, the three located occurrences 12, 18 and 24 yield identical similarity scores of 100%.
The skilled addressee will appreciate the limitations of this prior art technique in the case where a particular occurrence of the model is sought; in the present example, an occurrence neighbored on the left by a blank space is desired and this condition is satisfied only by occurrence 12 in the illustrated target image. This is a serious drawback for many applications.
FIGS. 3b, 2a, 2b and 2c together illustrate another example where more than one occurrence of a model is detected in a target image when using prior art techniques. Referring to FIG. 3b, the new model is defined as previously by a set of additive primitives 28. The dotted lines around the model primitives 28 are illustrative only and indicate that a blank space to the right of the model primitives 28 is sought; again, this wish is not defined in the model.
In the situation illustrated in FIGS. 2a, 2b and 2c, three occurrences 32, 36 and 40 of the model are located in the target image with the similarity scores shown. In FIG. 2a, a similarity score of, for example, 100% is computed. In FIGS. 2b and 2c, occurrences 36 and 40 produce identical scores of, for example, 85% since the vertical edge of the model is missing in occurrences 36 and 40.
The skilled addressee will appreciate that, if a threshold of say 70% is used for a positive match, all three occurrences 32, 36 and 40 would be considered matches for the model, while only occurrence 32 satisfies the above-identified wish. It will be appreciated that this is a serious disadvantage.
There is therefore a need in the industry for a method that will overcome the above-identified drawbacks.